package nz.ac.massey.groupproject.ecs2;

import java.util.ArrayList;

/*
 * All collidable shapes in our game are polygons.
 *
 * Currently, all polygons are convex.  If we need concave polygons in the future, we can break
 * them down to convex polygons. This should be fine as long as all shapes have a non-zero area.
 * (Otherwise a point can sneak in between the crack.)
 *
 * Currently, all polygons are explicit.  In the future, We may need implicit polygons to
 * approximate circles.  We will not worry about that for now.
 *
 * Explicit polygons are represented by the Polygon class.
 */

/*
 * Convex polygon represented by a list of vertices.
 *
 * No 2 points overlap.  No 3 points are colinear.
 * Some methods require >= 3 points, others accept < 3 points.  Check method documentation to find out.
 *
 * Vertices are sorted counter-clockwise.  The first point is farthest down (if two points are
 * equally low, the first point is the one to the left).
 *
 * The above is equivalent to sorting all edges by direction (0 ≤ angle < 360).
 *
 * XXX None of these constraints are checked by constructors. Caller must make sure they pass in valid data.
 * TODO check in DEBUG build
 *
 * In addition, we store the index of the point farthest up (break ties by picking the one to
 * the right) for quick 180 degree rotation.
 */
public final class Polygon {
	public final ArrayList<Vec2l>   vs;
	public final int                opposite_index;


	// ======================================== ctors ========================================
	public Polygon(long... coors)      { this(scalarpairsToVecs(coors));   }
	public Polygon(Vec2l... vertices)  { this(arrayToArrayList(vertices)); }

	public Polygon(ArrayList<Vec2l> vertices) {
		assert validateInput(vertices);

		vs = vertices;

		int topIndex = 0;
		for (int i = 1; i < vs.size(); i++) {
			var ydiff = vs.get(i).y - vs.get(topIndex).y;
			var xdiff = vs.get(i).x - vs.get(topIndex).x;
			if (ydiff > 0 || (ydiff == 0 && xdiff > 0))
				topIndex = i;
		}
		opposite_index = topIndex;
	}

	// These are slow. Try limit their use to debugging.
	public static Polygon canonicalise(Vec2l... vertices) {
		return canonicalise(arrayToArrayList(vertices));
	}
	public static Polygon canonicalise(ArrayList<Vec2l> vertices) {
		int ind = indexOfLowestPoint(vertices);
		int n = vertices.size();
		var newlist = new ArrayList<Vec2l>(n);
		for (int i = 0; i < n; i++)
			newlist.add(vertices.get( (ind+i)%n ));
		return new Polygon(newlist);
	}

	private static ArrayList<Vec2l> scalarpairsToVecs(long[] coors) {
		if (coors.length % 2 != 0) throw new RuntimeException("Internal Error: Polygon constructor called with odd number of arguments");

		var vertices = new ArrayList<Vec2l>(coors.length / 2);
		for (int i = 0; i < coors.length / 2; ++i) {
			vertices.add( new Vec2l(coors[i*2], coors[i*2+1]) );
		}
		return vertices;
	}
	private static ArrayList<Vec2l> arrayToArrayList(Vec2l[] vertices) {
		var list = new ArrayList<Vec2l>(vertices.length);
		for (var v : vertices)
			list.add(v);
		return list;
	}

	// either return true or throw exception
	// Only checks for likely human mistakes / algorithmic errors.  Does not check nulls, etc.
	private static boolean validateInput(ArrayList<Vec2l> vertices) {
		int n = vertices.size();

		if (n < 1) throw new AssertionError("Polygon must have at least 1 vertex");
		if (n == 1) return true;

		// check duplicates and colinear triplets and concavity (clockwise counts as concave)
		if (n == 2) {
			if (vertices.get(0)  .equals  (vertices.get(1)))
				throw new AssertionError("Denegerate line segment");
		} else {
			for (int i = 0; i < n; i++) {
				var P = vertices.get(  i      );
				var Q = vertices.get( (i+1)%n );
				var R = vertices.get( (i+2)%n );
				long cprod =  Q.sub(P)  .cprod(  R.sub(Q)  );
				if (0 == cprod) throw new AssertionError("Found 3 colinear points on polygon");
				if (0 >  cprod) throw new AssertionError("Not a convex polygon");
			}
		}

		// check for lowest point
		if (0 != indexOfLowestPoint(vertices))
			throw new AssertionError("0th vertex is not the (leftmost) lowest point");

		return true;
	}

	private static int indexOfLowestPoint(ArrayList<Vec2l> vertices) {
		final int n = vertices.size();
		assert n >= 1;

		long x0 = vertices.get(0).x;
		long y0 = vertices.get(0).y;
		int ind = 0;

		for (int i = 1; i < n; i++) {
			long y = vertices.get(i).y;
			long x = vertices.get(i).x;
			if (y < y0 || (y == y0 && x < x0)) {
				y0 = y;
				x0 = x;
				ind = i;
			}
		}
		return ind;
	}




	// ======================================== misc ========================================
	public Vec2l getV(int index) {
		return vs.get(index);
	}

	public Polygon translate(long xmove, long ymove) {
		var us = new ArrayList<Vec2l>( vs.size() );
		for (var P : vs)
			us.add(new Vec2l(P.x + xmove, P.y + ymove));
		return new Polygon(us);
	}

	// ======================================== heavy lifting ========================================
	/*
	 * Return 1 if point is outside.
	 * Return -1 if point is strictly inside.
	 * Return 0 if point is on the border.
	 *
	 * precondition: num vertices >= 3
	 *
	 * O(N)
	 */
	public int whereIs(Vec2l point) {
		final int n = vs.size();
		assert n >= 3;

		boolean strictlyInside = true;

		for (int i = 0; i < n; i++) {
			final Vec2l P = vs.get(  i  );
			final Vec2l Q = vs.get( (i+1)%n );
			final long cprod =  point.sub(P) .cprod( Q.sub(P) );
			if (cprod > 0) return 1;
			if (cprod == 0) strictlyInside = false;
		}

		return strictlyInside ? -1 : 0;
	}

	/*
	Compute Minkowski difference, which is used in collision detection.

	O(N) gift wrapping (sort of)
	TODO there's likely a way to compute partial hull in O(logN) time instead of doing the full hull in O(N).

	If aIndex and/or bIndex is given, they will tell you which vertex in the original polygon
	contributed to the i-th vertex in the resulting polygon.

	precondition: for each polygon, num vertices >= 2
	              (it probably works with n = 1 as well, but I didn't check)
	precondition: if aIndex and/or bIndex is present, they must be large enough
	              (maxsize = shapeA.numVertices + shapeB.numVertices is a safe upper bound)

	===== What is Minkowski difference =====
	Think of a solid shape as a mathematical set of points.
	The Minkowski difference between two shapes is defined as:

		minkowski_sum(shapeA, -shapeB)  =  { offset = a - b  |  ∀ a in shapeA,  b in shapeB }.

	===== How to use Minkowski difference =====
	Two shapes intersect iff Minkowski difference contains the origin.

	At time t, minkowski_sum(moved wall, -moved obj) contains O
	      <=>  minkowski_sum(init wall, -init obj) contains C = t * (velobj - velwall)

	Imagine inflating the wall and deflating the obj until the obj becomes a single dot.
	Also imagine moving the entire world to a new reference frame.  Now our little dot starts at the
	origin and travels at velocity vrel = vobj - vwall, and the wall is stationary.
	To avoid confusion, we will call the new object C, and the new wall "redzone".
	The original obj collides with the original wall iff C goes in redzone in this converted problem.

	Now we just wanna know whether C runs into redzone and if so, the earliest time of intersection.

	===== TODO explain the rest =====
	*/
	public static Polygon minkowskiDiff(Polygon sa, Polygon sb) {
		return minkowskiDiff(sa, sb, null, null);
	}
	public static Polygon minkowskiDiff(Polygon sa, Polygon sb,
	                                    /* outparam */ int[] aIndex, int[] bIndex) {
		int lenA = sa.vs.size();
		int lenB = sb.vs.size();
		assert lenA >= 2 && lenB >= 2;

		var newVertices = new ArrayList<Vec2l>( lenA + lenB );

		for ( int ia = 0, ib = sb.opposite_index
		    ; !(ia == lenA && ib == lenB + sb.opposite_index)
		    ; )
		{
			var P  = sa.vs.get(  ia    % lenA );
			var Q  = sb.vs.get(  ib    % lenB ).neg();
			var Pn = sa.vs.get( (ia+1) % lenA );
			var Qn = sb.vs.get( (ib+1) % lenB ).neg();

			newVertices.add( P.add(Q) );
			int ires = newVertices.size() - 1;
			if (null != aIndex)  aIndex[ires] = ia % lenA;
			if (null != bIndex)  bIndex[ires] = ib % lenB;

			long dircmp = (Pn.sub(P))  .cprod  (Qn.sub(Q));
			if (dircmp >= 0) ia++;
			if (dircmp <= 0) ib++;
		}

		// We don't shrink ArrayList because it's not gonna live long.
		return new Polygon(newVertices);
	}

	// If a point C starts at origin and travels along direction dir (t < 0 allowed), which edge / vertex
	// does it touch when it starts intersecting this solid polygon?
	//
	// Return [i, -1]      if C starts colliding by touching the i-th vertex.
	// Return [i, (i+1)%n] if C starts colliding by touching the i-th edge.
	// Return null         if they never collide.
	// If C barely scratches the surface of this polygon but never goes inside, this method
	// counts that as a collision.
	//
	// precondition: direction ≠ 0
	//               num vertices >= 3
	//
	// O(N)
	public int[] findCollisionSite(Vec2l dir) {
		// Cutting cake. Cut this polygon in half by direction vector (or the extension line of it).
		// Traverse the polygon; find out when it crosses the cutting line from left to right.
		final int n = vs.size();
		assert n >= 3           : "findCollisionSite() requires a polygon with nonzero area";
		assert dir.square() > 0 : "findCollisionSite(dir) does not work with dir = <0,0>";

		long side    = dir.cprod( vs.get(n-1) );               // + for left, - for right
		long newside = dir.cprod( vs.get( 0 ) );
		for (int i = 0;  i < n;  ++i) {                        // loop over edge <v{n-1}, v0>, <v0,v1>, <v1,v2>, ...
			final long nextside = dir.cprod( vs.get((i+1)%n) );

			if (side >  0 && newside <  0)                  return new int[]{ (i-1+n)%n, i };
			if (side >  0 && newside == 0)                  return new int[]{ i };
			if (side <= 0 && newside == 0 && nextside < 0)  return new int[]{ i };

			side = newside;
			newside = nextside;
		}
		return null;
	}
}
